package com.leetcode.algorithm.y22.m06;

/**
 * 33. 搜索旋转排序数组
 * 
 * https://leetcode.cn/problems/search-in-rotated-sorted-array/
 * 
 * @author jie.deng
 *
 */
class Question0033Solution01 {

	public int search(int[] nums, int target) {
		int left = 0;
		int right = nums.length - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			if (nums[mid] == target) {
				return mid;
			}
			if (nums[0] <= nums[mid]) {
				// [0,mid]是有序数组
				if (nums[0] <= target && target < nums[mid]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			} else {
				// [mid,right]是有序数组
				if (nums[mid] < target && target <= nums[right]) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			}
		}

		return -1;
	}

}